21-3

1

[CERC2017] Buffalo Barricades

考虑算出每个点最终被哪个矩形包含，这种情况下只有相互交叉的两个矩形可能存在覆盖关系。

$y$ $y$ 轴上恰好覆盖。

$x$ 坐标降序扫描线，用 set 维护射线的端点。因为矩形之间是编号小的覆盖在上面，所以考虑加入一条新的射线，如果被这条射线覆盖到的端点里面，有一个编号比它大，那么应当删除这个端点。

set 维护的实际上是这样一个结构：


1
----.
2
    |
3
--------.
4
        |
5
-----------.
6
           |

最终导致的结果，应当是端点在当前线之前的射线，编号都比当前线小。那么考虑一个点属于的矩形，就是覆盖这个点的那条射线。

$A$ $B$ $A$ $B$ 早出现。

考虑最后加入的矩形，答案一定是正确计算的。而一个没有被正确计算答案的矩形一定较早出现。

按照加入顺序倒序遍历所有矩形，那么找到在最终图形上，包含掉这个矩形的矩形，这只有一个，把答案合并到这上面即可。


xxxxxxxxxx
44
1
#include<bits/stdc++.h>
2
const int CN = 6e5 + 10;
3
using namespace std;
4
int read(){
5
    int s = 0, ne = 1; char c = getchar();
6
    for(; c < '0' || c > '9'; c = getchar()) if(c == '-') ne = -1;
7
    for(; c >= '0' && c <= '9'; c = getchar()) s = (s << 1) + (s << 3) + c - '0';
8
    return s * ne;
9
}
10
class PAIR{
11
  public: int x, y;
12
    bool operator < (const PAIR &o) const {return x ^ o.x ? x < o.x : y < o.y;}
13
    bool operator == (const PAIR &o) const {return x == o.x && y == o.y;}
14
} ; set<PAIR> S;
15
PAIR mp(int a, int b) {PAIR o; o.x = a, o.y = b; return o;}
16
int n, q, ans[CN], fa[CN], cnt[CN], to[CN], id[CN], X[CN], Y[CN], tp[CN];
17
bool cmp(int i, int j) {return X[i] ^ X[j] ? X[i] > X[j] : tp[i] > tp[j];}
18
int fd(int x) {return fa[x] ^ x ? fa[x] = fd(fa[x]) : x;}
19
int main(){
20
    freopen("_in.in", "r", stdin);
21
    n = read(); for(int i = 1; i <= n; i++) X[i] = read(), Y[i] = read(), id[i] = i;
22
    q = read(); for(int i = n + 1; i <= n + q; i++) X[i] = read(), Y[i] = read(), tp[i] = i - n, id[i] = i;
23
    sort(id + 1, id + n + q + 1, cmp);
24
    for(int p = 1, i; i = id[p], p <= n + q; p++){
25
        if(tp[i]){
26
            PAIR cur = mp(Y[i], tp[i]); S.insert(cur);
27
            set<PAIR> :: iterator it = S.find(cur); it++;
28
            if(it != S.end()) to[tp[i]] = (*it).y;
29
            it--; while(it != S.begin() && (*--it).y > tp[i]) S.erase(it), it = S.find(cur);
30
        }
31
        else{
32
            PAIR cur = mp(Y[i], 0);
33
            set<PAIR> :: iterator it = S.lower_bound(cur);
34
            if(it != S.end()) cnt[(*it).y]++;
35
        }
36
    }
37
    for(int i = 1; i <= q; i++) fa[i] = i;
38
    for(int i = q; i; i--){
39
        int x = fd(i), y; ans[i] = cnt[x];
40
        if(to[i]) y = fd(to[i]), cnt[y] += cnt[x], fa[x] = y;
41
    }
42
    for(int i = 1; i <= q; i++) printf("%d\n", ans[i]);
43
    return 0;
44
}

[HNOI2018] 排列

注意这个限制并不等价于反串的字典序最大！！能转化到字典序模型需要一个“绝对优势”。

$A$ $B$ ，代价是：

$\sum\limits_{i=1}^{|A|}(pre+i)w_i+\sum\limits_{i=1}^{|B|}(pre+|A|+i)w_i$

反过来的话，代价是：

$\sum\limits_{i=1}^{|B|}(pre+i)w_i+\sum\limits_{i=1}^{|A|}(pre+|B|+i)w_i$

$A$ $B$ $-|B|\sum\limits_{i=1}^{|A|}w_i+|A|\sum\limits_{i=1}^{|B|}w_i>0\Leftrightarrow \dfrac{1}{|A|}\sum\limits_{i=1}^{|A|}w_i<\dfrac{1}{|B|}\sum\limits_{i=1}^{|B|}w_i$ 。

对于确定的树形拓扑序，如果可以比较两个段哪个放在前面更好的话，一种通用的贪心方式就是每次找到最优的那个段，把它往父亲合并。

$O(n\log n)$ 。

扩展 KMP 复习

$s$ $s,t$ 的每个后缀的 LCP。

$z[i]=\text{LCP}(s,s[i:]]),p[i]=\text{LCP}(s,t[i:])$ $s[l,r]=s[:r-l+1]$ $i\le r$ ，可以发现有：

$z[i],p[i]\ge \min(z[i-l+1],r-i+1)$

$O(n)$ 。


xxxxxxxxxx
10
1
for(int i = 2, l = 0, r = 0; a[i]; i++){ // 枚举 a 的每个后缀
2
    if(i <= r) z[i] = min(z[i - l + 1], r - i + 1);
3
    while(i + z[i] <= la && a[i + z[i]] == a[z[i] + 1]) z[i]++;
4
    if(i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
5
}
6
for(int i = 1, l = 0, r = 0; b[i]; i++){ // 枚举 b 的每个后缀
7
    if(i <= r) g[i] = min(z[i - l + 1], r - i + 1);
8
    while(i + g[i] <= lb && b[i + g[i]] == a[g[i] + 1]) g[i]++;
9
    if(i + g[i] - 1 > r) l = i, r = i + g[i] - 1;
10
}

2

[CF780F] Axel and Marston in Bitland & [NOI2020] 美食家

$F_T=|f[T,1]...f[T,n]|$ $f[T,i]$ $T$ $i$ 的最大价值。

$W$ $W_{i,j}$ 表示：

$i\to j$ $W_{i,j}=val[j]$
$i\to j$ $W_{i,j}=-\infty$

$t_i$ $W_i$ $W$ $x_i$ $y_i$ 。

$W^{t_1-1}W_1 W^{t_2-t_1-1}W_2...$ 。

$O(k(5m)^3\log T)$ ，应该能有 35pts。预处理快速幂矩阵应该可以显著减小常数，但是这不本质。

$O(Tn^2)$ $T\le 52501$ ，应该有 40pts+25pts=65pts。

特殊性质 A 非常好做，这样应该就有 75pts。

$O(k(5n)^3\log T)$ . 75pts.

$1\times n$ $O(n^2)$ $O(n^3)$ 的。

$2^k$ $O((5n)^3\log T+(5n)^2k\log T)$ 。

[CODE FEST 2016 Grand Final] Water Distribution

对于一个块考虑，它最后整体的和一定是所有点权减掉用过的所有边权，那么最大化这个东西显然需要最小化用过的边权和，那么可以发现这个就是 MST 的边权和。

$O(2^n\text{poly } n)$ 。

$O(3^n)$ 枚举子集转移即可。

[51nod 1832] 后序与先序遍历

一棵二叉树如果某个节点只有一个儿子，那么无论这个儿子是它的左儿子或者右儿子，这棵树的先序遍历和后序遍历都是不变的。

$p[pos[i]+1]$ $i$ $p'[pos[i]-1]$ $i$ $p[pos[i]+1]=p'[pos[i]-1]$ 。

$cnt$ $2^{cnt}$ 。

[51nod 1231] 记分牌

$k$ $k$ $\ge \binom{k}{2}$ 。

[CF1303F] Number of Components

考虑如果正着做，唯一无法用并查集处理的问题是断掉两个联通块。

如果把这个过程反过来看，又相当于合并两个联通块，因此正反都做一遍即可。

$c_i\le c_{i+1}$ 保证了一个联通块至多进行一次断边或连边操作，因此是正确的。

细节？？？

3

高斯消元求自由元

[POJ1830] 开关问题

考虑按每个变量列方程，然后高斯消元，判断每个方程的主元是否存在即可求出自由元数量。

在实现上，由于可能无法消元成恰好的对角线矩阵，因此需要倒着枚举变量，回代方程。

$O(\dfrac{n^3}{\omega})$ .

[HAOI2018] 反色游戏

$m$ $n$ $2$ $cnt$ $2^{cnt}$ 。

XOR方程组的求解

$n$ $m$ 个变量的异或方程组。

$p$ $+1$ $i\in [1,m]$ $i$ 。

$i$ $q$ $p$ 个位置上，然后向下消元。

$p$ $a[p,i]=1$ $i$ $n-p+1$ 条方程都是无效的方程。

$0$ ，否则意味着方程组无解。

然后倒序枚举有主元的方程，我们总能解出该方程的主元的取值，然后向上回代即可。

$O(\dfrac{m^2n}{\omega})$

这样就有 60pts。


xxxxxxxxxx
10
1
int equ(){
2
    int p = 1, ans = 1;
3
    for(int i = 1; i <= m; i++){
4
        if(del[i]) continue; int q = p; while(q <= n && !a[q][i]) q++;
5
        if(q > n) {ans = add(ans, ans); continue;} swap(a[p], a[q]);
6
        for(int j = p + 1; j <= n; j++) if(a[j][i]) a[j] ^= a[p]; p++;
7
    }
8
    for(int i = p; i <= n; i++) if(a[i][m + 1]) return 0;
9
    return ans;
10
}

[HAOI2018] 染色

$f[k]$ $S$ $k$ $g[k]$ $k$ $S$ 次的方案数。

$\sum\limits_{i=0}^M W_if[i]$

$g[k]=\sum\limits_{i=k}^M\dbinom{i}{k}f[i]$

$f[k]=\sum\limits_{i=k}^M (-1)^{i-k}\dbinom{i}{k}g[i]$

$g[i]=\dbinom{M}{i}\dfrac{N!}{(S!)^i(N-iS)!}(M-i)^{N-iS}$

$f[k]=\sum\limits_{i=k}^M(-1)^{i-k}\dbinom{i}{k}\dbinom{M}{i}\dfrac{N!}{(S!)^i(N-iS)!}(M-i)^{N-iS}$

$=\dfrac{N!M!}{k!}\sum\limits_{i=0}^{M-k}\dfrac{(-1)^i}{i!}\times\dfrac{(M-(i+k))^{N-(i+k)S}}{(M-(i+k))!(S!)^{i+k}(N-(i+k)S)!}$

$a[i]=\dfrac{(-1)^i}{i!},b[i]=\dfrac{(M-i)^{N-iS}}{(M-i)!(S!)^i(N-iS)!}$ $M$ 。

$f[k]=\dfrac{N!M!}{k!}\sum\limits_{i=0}^{M}a[i]b[i+k]$

$O(n\log n)$ .

[Gym - 102978B] Bit Operation

考虑等价于每次选相邻的两个点，然后删掉其中一个。

枚举最后保留下来的点是哪个，那么考虑前后的点必须删掉，显然这个的方案数只和序列长度相关。

$i$ $2(i-1)$ $f[n]=f[n-1](2n-3)$ 。

$\dbinom{n-1}{i-1}$ 。

LGV 引理

$n$ $n$ $s\to t$ $\begin{Bmatrix}(u_i,v_i)\end{Bmatrix}$ $u_i=s_i,v_i=t_i$ ，且路径之间两两不相交。

$G$ $G_{i,j}$ $i$ $j$ $\text{det }G$ 。

4

[NOI2018] 你的名字

$S$ $T$ $T[pos:i]$ $i-pos+1$ 。

$nxt[]$ $T$ $O(|T|)$ 的。

$endpos$ $S[l':r]$ 中是否有这个串，也就可以判断这条边是否存在。

[HAOI2018] 字串覆盖

$S,T$ $T[l:r]$ $S[s:t]$ 中第一次出现的位置。

$T[l:r]$ $S$ $endpos$ 集合，我们只需要在线段树上二分即可。


xxxxxxxxxx
70
1
#include<bits/stdc++.h>
2
using namespace std;
3
#define lc ch[u][0]
4
#define rc ch[u][1]
5
const int CN = 1e5 + 10;
6
int read(){
7
    int s = 0, ne = 1; char c = getchar();
8
    for(; c < '0' || c > '9'; c = getchar()) if(c == '-') ne = -1;
9
    for(; c >= '0' && c <= '9'; c = getchar()) s = (s << 1) + (s << 3) + c - '0';
10
    return s * ne;
11
}
12
int n, q, pos[CN], pb[CN], len[CN << 2], nxt[CN << 2], fa[20][CN << 2], son[CN << 2][26], idx; char S[CN], T[CN];
13
void ins(char ch[], bool tp){
14
    for(int i = 1, u = 0, c; c = ch[i] - 'a', ch[i]; i++){
15
        if(!son[u][c]) son[u][c] = ++idx; u = son[u][c];
16
        if(tp) pos[i] = u; else pb[i] = u;
17
    }
18
}
19
int et(int p, int c){
20
    int u = son[p][c]; if(len[u]) return u; len[u] = len[p] + 1, p = nxt[p];
21
    while(p ^ -1 && !son[p][c]) son[p][c] = u, p = nxt[p];
22
    if(p == -1) return u; int d = son[p][c];
23
    if(len[d] == len[p] + 1) return nxt[u] = d, u;
24
    int v = ++idx; len[v] = len[p] + 1, nxt[v] = nxt[d], nxt[d] = nxt[u] = v;
25
    for(int i = 0; i < 26; i++) if(len[son[d][i]]) son[v][i] = son[d][i];
26
    while(p ^ -1 && son[p][c] == d) son[p][c] = v, p = nxt[p];
27
    return u;
28
}
29
class PAIR {public: int x, y;}; queue<PAIR> Q;
30
PAIR mp(int a, int b) {PAIR o; o.x = a, o.y = b; return o;}
31
void bd(){
32
    for(int i = 0; i < 26; i++) if(son[0][i]) Q.push(mp(0, i));
33
    while(!Q.empty()){
34
        int u = Q.front().x, c = Q.front().y; Q.pop(), u = et(u, c);
35
        for(int i = 0; i < 26; i++) if(son[u][i]) Q.push(mp(u, i));
36
    }
37
}
38
int rt[CN << 2], ch[CN * 70][2], cnt[CN], id[CN << 2], sidx; bool d[CN * 70];
39
void md(int &u, int l, int r, int p){
40
    if(!u) u = ++sidx; if(l == r) return (void)(d[u] |= 1);
41
    int m = (l + r) >> 1; p <= m ? md(lc, l, m, p) : md(rc, m + 1, r, p);
42
    d[u] = d[lc] | d[rc];
43
}
44
int mg(int x, int y, int l, int r){
45
    if(!(x * y)) return x + y; int u = ++sidx, m = (l + r) >> 1;
46
    d[u] = d[x] | d[y]; if(l == r) return u;
47
    lc = mg(ch[x][0], ch[y][0], l, m), rc = mg(ch[x][1], ch[y][1], m + 1, r);
48
    d[u] = d[lc] | d[rc]; return u;
49
}
50
int qu(int u, int l, int r, int s, int t){
51
    if(!d[u]) return 0; if(l == r) return l; int m = (l + r) >> 1, tmp;
52
    if(s <= m) {tmp = qu(lc, l, m, s, t); if(tmp) return tmp;}
53
    return m < t ? qu(rc, m + 1, r, s, t) : 0;
54
}
55
int main(){
56
    nxt[0] = -1, scanf("%s%s", S + 1, T + 1), n = strlen(S + 1), ins(S, 1), ins(T, 0), bd();
57
    for(int i = 1; i <= n; i++) md(rt[pos[i]], 1, n, i);
58
    for(int i = 1; i <= idx; i++) cnt[len[i]]++; for(int i = n; i; i--) cnt[i] += cnt[i + 1];
59
    for(int i = 1; i <= idx; i++) id[cnt[len[i]]--] = i;
60
    for(int p = 1, i; i = id[p], p <= idx; p++) if(nxt[i]) rt[nxt[i]] = mg(rt[nxt[i]], rt[i], 1, n);
61
    memcpy(fa[0], nxt, sizeof(nxt)), fa[0][0] = 0;
62
    for(int k = 1; k < 20; k++) for(int i = 1; i <= idx; i++) fa[k][i] = fa[k - 1][fa[k - 1][i]];
63
    q = read(); while(q--){
64
        int l = read(), r = read(), s = read(), t = read(), u = pb[t];
65
        for(int k = 19; k + 1; k--) if(len[fa[k][u]] >= t - s + 1) u = fa[k][u];
66
        if(t - s > r - l) puts("0");
67
        else printf("%d\n", max(0, qu(rt[u], 1, n, l + t - s, r) - t + s));
68
    }
69
    return 0;
70
}

$O(\dfrac{n\log n}{|T'|})$ ，考虑数据分治一下瞎搞就做完了，垃圾题。

[HAOI2018] 奇怪的背包

$P$ $P$ 的因子并不是很多。

$a[i]$ $(a[i],P)$ $2^s-1$ 种方法。

$P$ $O(\sigma_0(P)^2\log P)-O(1)$ 。

[HAOI2018] 苹果树

$i$ $i$ $sz[i](n-sz[i])$ 。

$sz[i]$ $i$ $i!$ $n-i$ $i$ $\dbinom{n-i}{sz[i]-1}sz[i]!$ $i$ $(i-1)^{\overline {n-i-sz[i]+1}}$ ，这部分乘起来就是：

$i!(i-1)^{\overline{n-i-sz[i]+1}}\dbinom{n-i}{sz[i]}sz[i]!=sz[i]!\dbinom{n-i}{sz[i]-1}(n-sz[i]-1)!i(i-1)$

答案是：

$\sum\limits_{i=2}^ni(i-1)\sum\limits_{s=1}^{n-1}\dbinom{n-i}{s-1}s·s!(n-s)!$

应该可以卷积。

[JSOI2019] 节日庆典

$O(n)$ 的 lyndon 分解解法：

$AA$ $|A|$ 个位置所在的 lyndon 串，那么最小表示法即是该字符串以这个 lyndon 串为起始的轮换

$O(n^2)$ 的，可以拿到 30pts 的好成绩。

先考虑一个错误的贪心：取字典序最小的后缀。这个贪心的错因在于接上前缀之后，字典序可能会变大，但是这启发我们，有用的后缀是字典序最小的那些后缀。

$s[i:]$ $s$ $t$ $p\in [1,\min |s|,|t|]$ $s_p<t_p$ $s[1:p-1]=t[1:p-1]$ 。

$O(\log n)$ 的。

$S$ $i$ $S_i$ $S_{i+1}\subseteq S_i\cup \begin{Bmatrix} i+1\end{Bmatrix}$ 。

$S_{i-1}$ $S_i$ $x\in S_{i-1}$ $S_i$ $y$ $x$ $y$ 。

$i$ 即可。

$i$ $x$ $y$ $|s[x:i]|>|s[y:i]|$ $s[y:i]$ $s[x:i]$ $s[x+i-y+1:]$ $s[1:n]$ 的大小关系即可，这个可以扩展 KMP 预处理。

$O(n\log n)$ 。

5

[CF547E] Mike and Friends

考虑类比两个串的做法，先建立广义前缀树，那么一次询问相当于是问某个子树内，线段树上一个区间里面所有出现次数的和。

乍一看这是个二维的东西，考虑有一维是没用的，能不能减少一维。

$u$ $[i,i]$ $u$ $i$ 这个串里的出现次数。

那么依然可以线段树合并来更新，然后就没了，但是空间怎么算都不够用。

有一个利用 fail 树性质的做法：

$+1$ $r=i$ $s_k$ 接受状态的那个子树权值的和，直接 BIT 维护即可。

$O(n\log n)$ $O(n|\Sigma|)$ 。

考虑这个题的启发是：

一个子串在这个串里面出现了多少次：SAM
一个前缀在这个串里面出现了多少次：KMP (Border)

那么：

一个串的子串在另一个串的子串里面出现了多少次：多串 SAM + 子树查询
一个串在另一个串中出现了多少次：多串 KMP + 子树查询

[SRM550, R1 div1] Conversion Machine

$S$ $T$ $i$ $a_i+3b_i$ 的形式。

$t$ $\sum step[i]+t\Sigma\le lim$ $t$ $X$ 。

$i$ $f_i$ $\sum\limits_{i=0}^X f_i$ $f_n=n![x^n]\prod\limits_i F_i(x)$ 。

考虑一个抽象的问题模型：

$m$ $n$ $k_i$ $i$ $\forall i\in[1,m], k_i\equiv a_i\pmod 3$ ，问有多少种不同的序列。两个序列不同，当且仅当某个位置涂上的颜色不同。
$m\le 11, n\le 10^9, 0\le a_i<3$

$G_n(x)=\sum\limits_{i}[i\bmod 3=a_n]\dfrac{x^i}{i!}$ $n![x^n]\prod\limits_i G_i(x)$ 。

$G_n(x)=\sum\limits_i\dfrac{1}{3} \sum\limits_{k=0}^2\omega_3^{k(i-a_n)}\dfrac{x^i}{i!}=\dfrac{1}{3}\sum\limits_{k=0}^2 \omega_3^{-ka_n}e^{\omega_3^kx}$ 。

$[x^n]\dfrac{n!}{3^n}\prod\limits_i(e^x+\omega_3^{-a_i}e^{\omega_3 x}+\omega_3^{-2a_i}e^{\omega_3^2x})$ 。

$3^n$ $\dfrac{AB^n}{3^n}$ $A$ $B$ $x$ 的系数和。

$\omega_3=e^{\text i\frac{2\pi}{3}}=\dfrac{\sqrt 3\,\text i-1}{2}$ $\text i^2=-3$ 扩域计算即可。

6

[NOIAC D1 A] 异或

$a,b,c\in \mathbb N$ $a\le b\le c$ $a\oplus c\ge \min a\oplus b, b\oplus c$ 。

证明：

$a<b<c$ 的情况，首先对高位考虑。

$a,b,c$ 的最高位均相同，可以规约到去掉最高位时的情况；

$a,b,c$ 的最高位均不相同，那么结论直接成立；

$a,b$ $c$ 不同，那么结论直接成立；

$b,c$ $a$ 不同，那么结论直接成立。

那么判断一个集合合法，只需要将其排序即可。

$p$ $2^i\ge x$ $i$ $a[]$ $p$ $p$ 位互不相同。

那么一个组里面只能不选，选一个或者选两个，算出每组的方案数相乘即可。

$\ge x$ ，直接 Tire 维护即可。

$x=0$ ，特判即可。


xxxxxxxxxx
13
1
#define lc ch[u][0]
2
#define rc ch[u][1]
3
int rt, ch[CN * 60][2], sz[CN * 60], idx;
4
void ins() {}
5
int qu(int u, int dep, LL x, LL y){ // ai ^ x <= y
6
    if(dep < 0) return sz[u];
7
    if((y >> dep) & 1){
8
        if((x >> dep) & 1) return qu(lc, dep - 1, x, y);
9
        return qu(rc, dep - 1, x, y);
10
    }
11
    if((x >> dep) & 1) return sz[lc] + qu(rc, dep - 1, x, y);
12
    return sz[rc] + qu(lc, dep - 1, x, y);
13
}

7

[NOIAC D2 A] 矩阵填数

$n\times m$ $[1,m]$ $q$ $[(x_1,y_1),(x_2,y_2), v]$ $(x_1,y_1)$ $(x_2,y_2)$ $v$ ，求有多少种方案。

考虑如果限制矩形均不相交，那么答案很容易计算。

$v$ $v$ $v$ 相等呢？这就比较难处理。

$v$ 互不相同的情况，那么显然将矩形排序，然后枚举一个矩形，就只需要算出在它前面的的矩形，与它的交覆盖的总面积，这部分是由这个矩形控制的。

$v$ $S$ $S$ 个矩形均不满足限制的方案数容斥，这个很容易计算。

$v$ $v$ 乘起来。

$cu[S]$ $cu[S]=\sum\limits_{T\subseteq S} (-1)^{|T|-1}ca[T]$ ，那么直接高维前缀和计算即可。

$O(n2^n)$ 。

Manacher 复习

$O(n)$ 的复杂度。

$\lceil\dfrac{l}{2} \rceil$ $l$ 表示以该位置为回文中心的串的最长长度。

$s$ $\lfloor\dfrac{|s|}{2} \rfloor$ 这个位置。

$[l_0,r_0]$ $r[i]\ge \min p+r[p]-i,r[2p-i]$ $[p-r[p], p+r[p]]$ $O(n)$ 。

$s$ $s[i:]$ $z[i]$ 。

$[l,r]$ $i\le r$ $z[i]\ge \min z[i-l+1],r-i+1$ $O(n)$ 。

最长回文前后缀这种东西还是回文树吧...

8

[CF573E] Bear and Bowling

$O(n!)$ $O(2^n)$ $O(2^n)$ $O(n^2)/O(\text{poly }n)$ DP，这个要记清楚了。

$f[i,j]$ $i$ $j$ 个，可以发现这个状态是容易转移的。

$f[j]$ $j$ $i$ ，更新到的一定是一段后缀。直接数据结构维护就好了。

[HDU3306] Another Kind of Fibonacci

$f^2_n=(Af_{n-1}+Bf_{n-2})^2=A^2f^2_{n-1}+B^2f^2_{n-2}+2AB f_{n-1}f_{n-2}$ ；

$f_{n}f_{n-1}=(Af_{n-1}+Bf_{n-2})f_{n-1}=Af_{n-1}^2+Bf_{n-2}f_{n-1}$ 。

这样就可以维护了。也就是说维护乘积求和的时候要试图找乘积的递推关系。

$\begin{matrix}|s_n &f^2_n&f^2_{n-1}&f_nf_{n-1}|\end{matrix}$ $\begin{vmatrix}1&0&0&0\\A^2&A^2&1&A\\B^2&B^2&0&0\\2AB&2AB&0&B\end{vmatrix}$ 。

特征方程复习

一阶：构造等比递推

$x_n=px_{n-1}+q$ ，尝试构造等差数列：

$d$ $x_n-d=p(x_{n-1}-d)$ $x_n=px_{n-1}+(1-p)d$ $(1-p)d=q,d=\dfrac{q}{1-p}$ 。

$\begin{Bmatrix}x\end{Bmatrix}-d$ $x'_n=p^nx'_0$ $x'_0=x_0-d,x'_n=x_n-d$ 。

高阶

$x_n=ax_{n-1}+bx_{n-2}$ $x^n$ $x_{n}$ $x^n=ax^{n-1}+bx^{n-2}$ $x^2-ax-b=0$ 。

$X_0,X_1$ $A,B$ ，使得：

$x_n=AX_0^n+BX_1^n$

使用前两项解出系数即可。

[HDU2256] Problem of Precision

$(\sqrt 2+\sqrt 3)^{2n}\bmod 1024$ $\lfloor(\sqrt 2+\sqrt 3)^{2n}\rfloor\bmod 1024$ 。

$(\sqrt 2+\sqrt 3)^{2n}=(5+2\sqrt 6)^n$

$(5+2\sqrt 6)^n+(5-2\sqrt 6)^n = 2\text{Re}[(5+2\sqrt 6)^n]$ 。

$(5-2\sqrt 6)=0.101...$ $1$ 的数字。

$\lfloor(5+2\sqrt 6)^n\rfloor=\lfloor2\text{Re}[(5+2\sqrt 6)^n]-eps\rfloor$ $0<eps<1$ 。

$2\text{Re}[(5+2\sqrt 6)^n]-1$ ，扩域即可。

树状数组上倍增

$d[i]$ $[i-\text{lowbit}(i)+1,i]$ $[i+1, i+2^k]$ $d[i+2^k]$ $k$ $i$ 的 lowbit，我们发现倍增过程恰好满足这个性质。

[联合省选2020 A] 冰火战士

考虑先把两个数组都升序排序，以下做法基于该结论讨论：

$si(i)\le sf(i)$ $i$ $si(j)>sf(j)$ $j$ $i,j$ 中的一个。

$T$ $ai$ $af$ $af$ $-1$ ，用当前的总和减掉前缀和即可。

$O(n\log n)$ 。

灵光一现

$S,T$ 内共出现了多少个本质不同的子串。

解一：对这两个字符串建广义 SAM（Trie 树上建 SAM），统计每个节点的贡献即可。
$S$ $T$ $S,T$ $S,T$ $T$ $S$ $T$ $T[i]$ $\max(0, ml-len_T[nxt_T[u]])$ $ml$ 是当前匹配长度。

基环树的 Prufer 序列构造

每次找到编号最小的一个叶子，把它的父亲加入序列。如果它的父亲在环上，那么不删除；否则删除这个父亲。

$u$ $d_u-1$ $u$ $d_u-2$ ，并且序列中最后一个点一定是环上的点，并且序列的长度 = 点数 - 环长。

如果这个时候已经确定了环的形态，那么就可以确定这个基环树。这里的形态指的是有哪些点，以及点的顺序。

注意一个大环没办法用这种构造表出，或者说表出的结果是空序列 + 大环。

[Code FEST 2017 R3 J] Unicyclic Graph Counting

$n$ $d_1...d_n$ ，求有多少个满足该度数序列的有标号基环树。

$\sum\prod \dfrac{1}{(d_i-k)!},k=1/2$ $O(n^2)$ 。

$n$ $\dfrac{(n-1)!}{2}$ 种形态。

毒瘤

$n$ $n^{n-1}$ $n$ 个点的有标号基环树有多少种形态？

树是简单图，因此不能有自环或者重边。

$\dfrac{(n-1)!}{2}+\dfrac{1}{2}\sum\limits_{l=3}^{n-1}n^{\underline l}n^{n-l-1}$

OEIS-A057500

9

同余最短路

$0$ $a_i,i\in[1,n]$ $[0,m]$ $m$ $\min a_i$ 很小。

$b=\min a_i$ $a_i$ $k_ib+r_i$ $k_i\ge 1, 0\le r_i<b$ 。

$d[i]=x$ $x\bmod b=i$ $x$ $d[i]+pb$ $i\in[0,b)$ $d[i]$ ，我们就能解出问题的答案。

$a_i$ $j\in[0, b)$ $(j,(j+a_i)\bmod b,a_i)$ $d[i]$ $O(b)$ $O(bn)$ $0$ $i$ 的最短路，使用 Dijkstra 求解即可。

[WC2016] 论战捆竹竿

$0$ $a_i$ $[0, w-n]$ $a_i=n-|\text{Border}[i]|$ 。

$\min a_i$ $O(n)$ $O(n^2)$ 的，这样有 50pts。

$s$ $O(\log |s|)$ 段等差数列。

不会了/kk

reflect

线段树合并的时候，判断要这样写：


xxxxxxxxxx
1
1
if(!u || !v) return u | v;

不要用乘积！！乘积会溢出，很可能被对着卡！！

对拍必须写，先打好暴力。第一遍先打暴力，第二遍再想题，注意时间。

[THUSCH2017] 大魔法师

先把信息写成向量的形式，然后通过矩阵来进行变换。

$\begin{vmatrix}A_i &B_i&C_i \end{vmatrix}$

$\begin{vmatrix}1&0&0\\1&1&0\\0&0&1 \end{vmatrix}$ ；

$\begin{vmatrix}1&0&0\\0&1&0\\0&1&1 \end{vmatrix}$ ；

$\begin{vmatrix}1&0&1\\0&1&0\\0&0&1 \end{vmatrix}$ ；

$\begin{vmatrix}v&0&0 \end{vmatrix}$ ；

$\begin{vmatrix}1&0&0\\0&v&0\\0&0&1 \end{vmatrix}$ ；

$\begin{vmatrix}1&0&0\\0&1&0\\0&0&0 \end{vmatrix}$ $\begin{vmatrix}0&0&v \end{vmatrix}$ 。

矩阵的运算满足结合律和分配律，因此维护乘法和加法标记即可。

$d[k]m[k]+r[k]$ ，区间整体加的时候直接加在外面，区间整体乘的时候两边都要乘。注意永远都是右乘。

$a\times b$ $a[i][j]=0$ 的情况，也就直接 continue，常数会小很多。卡到了 loj 第三页，我不行。

当构造函数被调用很多次而可以特判取代时，不写构造也能减少常数。

10

[ZJOI2013] K大数查询

$mid$ $\le mid$ $>mid$ 进行分治。

$c\le mid$ $[l,r]$ $\le mid$ $sum(l,r)\ge c$ 。

$O(n\log ^2n)$ 。

[AGC001 E] BBQ Hard

$\sum\limits_{i=1}^n\sum\limits_{j=1}^{i-1}\dbinom{A_i+A_j+B_i+B_j}{A_i+A_j}$ ，显然它等于：

$\dfrac{1}{2}\left[ \sum\limits_{i=1}^n\sum\limits_{j=1}^n \dbinom{A_i+A_j+B_i+B_j}{A_i+A_j} -\sum\limits_{i=1}^n\dbinom{2(A_i+B_i)}{2A_i} \right]$

$\dbinom{A_i+A_j+B_i+B_j}{A_i+A_j}$ $(-A_i,-B_i)$ $(A_j, B_j)$ 的方案数，每步只能向上或者向右走。

$(-A_i,-B_i)$ $1$ $(A_i,B_i)$ 处统计答案。

$O(n+V^2)$ $V$ 是值域。

Border 的四种求法

$0<r\le |s|$ $\forall i\in[1,|s|-r], s_i=s_{i+r}$ $r$ $s$ $per(s)$ 。
$p,q$ $s$ $p+q\le |s|$ $(p,q)$ $s$ 的周期。
$p,q$ $s$ $p+q-(p,q)\le |s|$ $(p,q)$ $s$ 的周期。

Periodicity Lemma 指出了周期之间是存在联系的，这个联系基于一个基本事实：周期的倍数依然是周期。

存在结论：

$s[:k]$ $s$ $|s|-k$ $s$ 的周期。

$2k\le n$ $AXA$ $A$ $X$ $|AX|=|s|-|A|$ 。

$2k>n$ $XA$ $A$ $A$ $XA$ $|A|>|X|$ $X$ $A$ $X$ $A$ $XA'$ $|X|=|XA|-|A|$ 是串的周期。

根据上面的推导，不难发现反过来也是成立的：

$r$ $s$ $s[:|s|-r]$ $s$ 的 Border。

也就是说一个串的 Border 和一个串的周期是本质相同的集合，在表现上形成互补的关系。

[HDU3746] Cyclic Necklace

求整串的最短周期，相当于求串的最长 Border，直接 KMP 即可。

[WC2019 Lecture] 周期串查询

$s[l:r]$ $X^kX'$ $k\ge 2$ $X'$ $X$ $-1$ 。

即求最小周期，是下面这道题的弱化版。直接求出所有 runs，那么答案相当于一个矩形前缀求最小，直接离线二维数点即可。

[BJWC2018] Border 的四种求法

$a,b$ $2|a|\ge b$ $a$ $b$ $per(a)$ 的等差数列。
$s$ $s$ $\log |s|$ 个等差数列。

11

[Gym102978H] Harsh Comments

$n$ $a_i$ $m$ $b_i$ $\frac{a_i}{s}$ $\frac{b_i}{s}$ $s$ 是当前状态下剩余所有物品权值的和。求删光所有 A 物品的时间的期望。

$n,m\le 100,A_i\le 100, B_i<998244353$

$T$ ，求这个子集的元素至少有一个被删掉的时间的期望。

$v$ $\sum\limits_{i\not\in T} \dfrac{a_i}{a_i+v}+\sum\limits_{i\not \in T}\dfrac{b_i}{b_i+v}+1$ 。

$p_i$ $\sum\limits_{T}(-1)^{|T|-1}\left(\sum\limits_{i\not \in T}\dfrac{p_i}{p_i+si(T)}+1\right)$ 。

$=\sum\limits_T (-1)^{|T|-1} \sum\limits_{i\not \in T} \dfrac{p_i}{p_i+si(T)}+\sum\limits_{T}(-1)^{|T|-1}$

$=1+\sum\limits_T (-1)^{|T|-1} \sum\limits_{i\not \in T} \dfrac{p_i}{p_i+si(T)}$

$=1+\sum\limits_{i=1}^{n+m}\sum\limits_{s>0}(-1)^{s-1}\dfrac{p_i}{p_i+s}\times []$

$[]$ $i$ $s$ ，求它们的系数和。

$O(n^2|V|)$ $i,s, p$ $O(n^3|V|^2)$ 。

$f[]$ $O(n^2|V|)$ $i$ $(1+x^{p_i})$ $O(n|V|)$ 。

$O((n+m)n|V|)$ $V$ $a_i$ 的值域。

矩阵转置与转置原理

$n\times m$ $A$ $m\times n$ $B$ $B$ $i$ $A$ $i$ $B=A^T$ 。
$V=E_1E_2E_3...E_n$ $V^T=E_n^TE_{n-1}^T...E_1^T$ 。

[bzoj3583] 杰杰的女性朋友

$n$ $k$ $P_i=\begin{vmatrix}in[i,1]&in[i,2]&...&in[i,k] \end{vmatrix}$ $k$ $Q_i=\begin{vmatrix}ou[i,1]&ou[i,2]&...&ou[i,k] \end{vmatrix}$ 。

$i,j$ $i\to j$ $Q_i·P_j$ 种走法。

$q$ $u,v,d$ $u$ $v$ $d$ 条边的路径有多少条。

$q\le 50, n\le 1000,k\le 20, d\le 10^9$

$QP^T$ $(QP^T)^d$ $QP^T$ $n\times n$ 的矩阵，这样显然不行。

$d$ $u_0(QP^T)^d=u_0Q(P^TQ)^{d-1}P^T$ ，中间那一部分就可以快速幂了。

$u_0Q\left(\sum\limits_{i=0}^{d-1}(P^TQ)^i\right)P^T$ $D=P^TQ$ ，考虑中间那一部分怎么计算。

$\sum\limits_{i=0}^{d-1} D^i$ $A_i=D^{2^i},B_i=\sum\limits_{j=1}^{2^i}D^j$ $B_i=B_{i-1}+B_{i-1}A_{i-1}=B_{i-1}(A_{i-1}+I)$ 。

$d-1$ $B$ $A$ 的形式。

12

训练 31 订正

$O(n\log ^3n)$ $O(n\log n)$ ，常数大的一匹，没过去。

$\sqrt{n}$ $\sqrt n$ $\log$ $O(q\sqrt n\log n)$ 。

$\log n$ $q\log n$ $q\sqrt n\log n$ $O(n\log ^2n+q\sqrt n\log ^2n)$ ，看起来都不如直接点分治，但是感觉会松一些。

$q\log n$ $O(n\log ^3n)$ $q\log ^2n$ $O(n\log ^3n+q\log ^3n)$ $O(n\log|V|)$ 。

$\log$ $\log$ 很松，没用的线段直接 return 即可。

$1\to n$ 的方案数。

$f[i]$ $i$ $i$ $f[i,j]$ $i$ $j$ 段路径未结束。因为路径没有结束，所以一段路径的末端一定是 R 点或者 B 点。

$i$ $O(n^2)$ 。

13

考虑用 LCT 维护森林，然后两个子树合并的时候，现在的并集应该等于两个部分的大小加起来，然后减掉交集。

考虑这个交集，实际上就是上一次合并时这两两个连通块的并集，因为显然新加入的元素不可能有交。

于是直接拿 LCT 维护每棵树的答案，合并分裂都解决了，每次分裂的时候，在这条边上记录一下现在的并集大小即可。

$O(n\log n)$

15

[雅礼集训 2017 Day1] 字符串

$s,w$ $a,b$ $[l_i,r_i]$ $O(q(n+|s|+m\log n))$ 但是很松，估计可以过 50pts。

$qk\le 10^5$ ，然后数据分治...

B. Replicate Replicate Rfplicbte

C. Longest Rivers

[CF 1276F] Asterisk Substrings

$\emptyset ,*,s,s_1*,*s_2,s_1*s_2$ $\emptyset,*$ $s$ $s_1*,*s_2,s_1*s_2$ 三种情况，并且这三种情况里是可能算重的。

$*$ $s_1*s_2$ $s_1*s_2$ 这种情况。

$s_1$ $s_2$ 是均相同的，也就是需要计算一些后缀组成的集合的本质不同前缀数量。后者显然等于这些后缀的长度和减掉排序后相邻串的 LCP。

$O(n\log ^2n)$ ，这样需要同时建立前缀树和后缀数组结构。

一些后缀的本质不同前缀数量，等于这些后缀在后缀树上对应节点到根的链长并。实际上可以直接求 dfs 序，然后按照这个启发式合并。

$O(1)$ LCA。定义后缀结构体，维护这个结构体的 set，然后按 dfs 序倒序遍历前缀树，维护 endpos 整体 +2 的集合和它的权（set），然后启发式合并，每次合并相当于取消掉原来两个的贡献，加入新加入的两部分贡献。

$O(n\log ^2n)$

最小回文划分

$s$ $\log |s|$ 段等差数列。

只需要考虑对最长回文后缀应用 WPL 即可。

$di[x]=len[x]-len[nxt[x]]$ $nxt[x]$ $di[x]\neq di[nxt[x]]$ $slink[u]$ 均指向上一段等差数列的末端。

$g[x]$ $x$ $x$ $f[]$ $g[x]$ $g[nxt[x]]$ $f[i-len[lk[x]]-di[x]]$ 。

$g[]$ $f[i]$ $O(n\log n)$ 。


xxxxxxxxxx
16
1
void clr() {nxt[0] = len[0] = -1, lst = idx = 1;}
2
int p = lst, c = ch[i] - 'a';
3
while(ch[i - len[p] - 1] ^ ch[i]) p = nxt[p];
4
if(!son[p][c]){
5
    son[p][c] = ++idx, len[idx] = len[p] + 2;
6
    int pp = nxt[p]; while(pp ^ -1 && ch[i - len[pp] - 1] ^ ch[i]) pp = nxt[pp];
7
    nxt[idx] = pp ^ -1 ? son[pp][c] : 1;
8
    di[idx] = len[idx] - len[nxt[idx]];
9
    lk[idx] = di[idx] ^ di[nxt[idx]] ? nxt[idx] : lk[nxt[idx]];
10
}
11
lst = son[p][c], n++, f[i] = 2e9;
12
for(int j = lst; j > 1; j = lk[j]){
13
    g[j] = f[i - len[lk[j]] - di[j]];
14
    if(di[j] == di[nxt[j]]) g[j] = min(g[j], g[nxt[j]]);
15
    f[i] = min(f[i], g[j] + 1);
16
}

$nxt[x]$ $x$ $x$ 的 Border！！

OI-Wiki

UVA11584

[CF 932G] Palindrome Partition

$A=B$ $B^r$ $A$ $C$ $C$ 必然是回文串。例如：


xxxxxxxxxx
3
1
A : abcd
2
B : abcd
3
C : ad bc cb da

$s_k^r$ $s_1$ $s_{k-1}^r$ $s_2$ $s^r[|s|/2+1:]$ $s[:|s|/2]$ $s'$ $t$ $s'$ 中双射一个偶回文子串。

$s'$ 的偶回文划分数量，这个只需要钦点每个状态都只出现偶回文串即可。

$O(n\log n)$

[CF 906E] Reverses

$f[i]$ $i$ $f[i]=f[i-1](s[i]=t[i])$ $f[i]=\min\limits_jf[j]+1$ $j$ $s[j:i]=t^r[n-i+1:n-j+1]$ 。

~~由于 DP 数组有单调性~~ $j$ $t$ $s[i]$ $t[n-i+1]$ 向后求一个反向 Border，显然它的本质和区间 Border 相同，然而区间 Border 是众所周知的不可做问题。

考虑两个对应位置的子串反转其中一个会相等，就等价于两个子串插起来之后得到的是一个偶回文串。

$O(n\log n)$

16

[CF590E] Birthday

一眼秒了。

先建出 fail 树，显然一个串的子串是它在 fail 树上的祖先。我们希望不存在偏序关系，等价于求 fail 树的最长反链，也就是传递闭包后的最小链覆盖。

$\infty$ 边，然后答案是点数 - 最大流。

求方案？

考虑求出拆点二分图的最大独立集，具体操作是：

$i$ 就在最长反链里。

[CF700E] Cool Slogans

前缀树上的最长链？有一个问题是，转移时应不应当加一。

如果父节点在子节点中出现了两次以上的话，就应该加一。否则可以把父节点替换成这个点，然后不加一。

线段树合并即可。

坑点：转移的时候需要维护出现在这个节点实际上是哪个点，因为可能不选择这个节点。

坑点：必须从树根往下 DP，因为倒过来的过程可能有多种不同的选择，但是从上向下只有一种选择。

[HDU5390] Tree

可持久化 Tire 的带修只能类似于线性基带修那样，线段树分治来解决。

$\log$ $O(n\log n)$ $O(n\log ^2n)$ 。

$[l_i,r_i]$ 这一段位置内有效，维护每个区间对应集合的 DS”。

$\log$ 段区间，然后由于查询是单点查询，所以标记永久化，在线段树的每个节点上，维护对应集合的 DS。

$O(n\log n\Epsilon(n))$ $O(n\log n\Omega(n))$ $\Epsilon(n)$ $\Omega(n)$ 是该 DS 一次操作的时间复杂度。

通常理解的线段树分治相当于对时间轴可持久化，本质上还是解决上面的模型。

实际上是两种角度！！一种角度是用 BIT 那样的单层结构实现可持久化结构，另一种角度是用线段树或分块那样的多层结构实现可持久化结构。

本质上分块是三层线段树！！

$O(n\log n\omega)$ 。
$\log$ $\log$ $O(n\log ^2n)$ 。
$\log$ $O(n\log n\omega)$ 。

考虑原问题，首先想到可以树上可持久化 Tire，但是没有树上 BIT 所以无法支持修改，这样不行。

因为所有查询路径都是从根出发的，这种情况下用不着树链剖分！！树链剖分解决的是任意两个特殊点之间，路径查询的问题。如果一个端点固定，可以被 dfs 序完美代替，因为这个时候另一个点的影响区间在 dfs 序上一定是连续的！！

$O(n\log n\omega)$ ，空间上过不去。

$O(n\log n\omega)$ $O(n(\log n+\omega))$ 。

回文树的双端插入和后端删除

论文

$pre,suf$ $pre/suf$ $nxt[]$ 即可。

[HDU5421] Victor and String

从前后段插入字符，询问本质不同的回文串数量和所有回文串数量。

$endpos$ 集合大小之和，这个考虑贡献，每新建一个字符直接求祖孙链和即可。


xxxxxxxxxx
15
1
int nxt[CN], len[CN], son[CN][26], lstl, lstr, pl, pr, idx;
2
void clr(){
3
    for(int i = 0; i <= idx; i++) memset(son[i], 0, sizeof(son[i])), nxt[i] = len[i] = 0;
4
    nxt[0] = len[0] = -1, lstl = lstr = idx = 1;
5
}
6
void ins(int &lst, int c, int i, int tp){
7
    int p = lst; while(ch[i + tp * (len[p] + 1)] ^ ch[i]) p = nxt[p]; 
8
    if(!son[p][c]){
9
        son[p][c] = ++idx, len[idx] = len[p] + 2; int pp = nxt[p];
10
        while(pp ^ -1 && ch[i + tp * (len[pp] + 1)] ^ ch[i]) pp = nxt[pp];
11
        nxt[idx] = pp ^ -1 ? son[pp][c] : 1, ed[idx] = ed[nxt[idx]] + 1;
12
    } 
13
    lst = son[p][c], ans += ed[son[p][c]]; 
14
    if(len[lst] == pr - pl + 1) lstl = lstr = lst; // border case!
15
}

$fail[u,c]$ $u$ $c$ $v$ $v$ $u$ $v$ $c$ 。

$fail[u]$ $fail[u]$ $fail[nxt[u]]$ $O(1)$ $nxt[u]$ $x$ $fail[u,x]=nxt[u]$ 。

$u$ $c$ $c$ 。

$O(n|\Sigma|)$ $O(n\log |\Sigma|)$ 。

在 Trie 上建立回文树 / 末端删除：可以发现后者完全是前者的子问题，而前者可以通过上面的算法简单实现。

$lst[]$ 指针也必须可持久化才行。

类似的处理办法还出现在了 KMP 自动机中。本质上这的确是一类自动机，只不过没有起始状态和接受状态。

[HDU5394] Trie in Tina Town

就是上面的模板。


xxxxxxxxxx
22
1
/* 
2
to[u][c] 表示如果 u 后面新增一个字符 c, 跳 nxt 的执行结果 
3
在递归子节点之前把子节点的 to[] 更新成正确的值即可
4
*/
5
int len[CN], nxt[CN], lst[CN], son[CN][26], to[CN][26], idx;
6
void dfs(int u, int dep){
7
    for(int k = hd[u]; k; k = E[k].nxt){
8
        int v = E[k].to, c = E[k].c, p = lst[u]; ch[dep] = c;
9
        if(ch[dep - len[p] - 1] ^ ch[dep]) p = to[p][c];
10
        if(!son[p][c]){
11
            son[p][c] = ++idx, len[idx] = len[p] + 2; int pp = nxt[p];
12
            if(pp == -1) nxt[idx] = 1; 
13
            else{
14
                if(ch[dep - len[pp] - 1] ^ ch[dep]) pp = to[pp][c];
15
                nxt[idx] = son[pp][c];
16
            }
17
            memcpy(to[idx], to[nxt[idx]], sizeof(to[nxt[idx]]));
18
            if(dep > len[nxt[idx]]) to[idx][ch[dep - len[nxt[idx]]]] = nxt[idx];
19
        }
20
        lst[v] = son[p][c], dfs(v, dep + 1);
21
    }
22
}

17

[LOJ517] 计算几何瞎暴力

考虑一次排序之后，下一次排序之前，这个数组每时每刻都可以被划分成两个部分：前面一部分是有一定顺序的，后面一部分则按照加入顺序排列。

考虑这一段之间内，前面那一部分，一定是先是升序的，然后某次 4 操作之后，变成了无序的。但是不考虑这次 4 操作，依然是升序的。如果我们给 4 操作打一个 lazy tag，那么这部分就是升序的。

$k$ 大之和；后面一部分拆开位拿数组维护，询问相当于求前缀和。

1 操作，直接接在后面那部分。

$\omega$ 个信息，表示这个子树每一位上有多少 1。

$x$ $a_i\oplus x$ 。

$t\gets t\oplus x$ ，然后把数组里面的数字都加入 Trie。

$O(n\omega^2)$ 。

[CF963D] Frequency of String

$m$ $L$ $s$ $endpos$ $O(|s|\sqrt L)$ 的。

$O(\sqrt L)$ $O(|s|)$ $endpos$ 。

于是就 set 启发式合并然后直接做了。

[CF587F] Duff is Mad

先建 fail 树。考虑一个串的所有出现位置是它在 fail 树中的子树。

$s_1...s_r$ $s_k$ 中出现了多少次。

$1$ $n$ $s_i$ $s_i$ $+1$ $+1$ $k$ ，就相当于对 AC 自动机上的一条路径求和。

$\le \sqrt n$ $\ge \sqrt n$ $\sqrt n$ $cnt[]$ $j$ 种长串有多少个。长串的答案我们直接单独维护，每次子树加，枚举长串直接答案加权即可。

$O(n\sqrt n)$

[NEERC2015] Distance on Triangulation

$L$ $R$ $p_1,p_2$ $L,R$ $p_1,p_2$ 中的一个。

然后我们就可以找一条边使得左右两边分的尽量均匀，然后从这两个点开始广搜，然后分治下去计算。

形式化的理解，相当于在维诺图（对偶图？）上边分治，因为这里维诺图一定是一棵树，可以简单证明。

$2$ 的点，然后把这个点删掉，然后给这个区域新建一个点，然后把新点挂在对边上。

每删掉一条边的时候，把当前的点个边上的点连起来。

slstxdy

$O$ $S$ $S'\subseteq S$ $S'$ $O$ 。

数据保证任意三个点不共线。

不会做/kk

18

$n$ $n=\binom{a}{1}+\binom{b}{2}+\binom{c}{3}$ 。

[LOJ6055] 一道数学题

$f(n)=n^k+\sum\limits_{i=1}^{n-1} i^k2^{n-1-i}$ $i$ $k$ 次多项式。

$\begin{align} &=2^{n-1}\sum\limits_{j=0}^k \begin{Bmatrix}k\\j \end{Bmatrix}j!\sum\limits_{i=1}^{n-1} \dbinom{i}{j}2^{-i}\\&=2^{n-1}\sum\limits_{j=0}^k \begin{Bmatrix}k\\j \end{Bmatrix}j!S_j(n) \end{align}$

$S_k(n)-1/2S_k(n)$ $S_k(n)$ $S_{k-1}(n)$ 的关系。好思路！！

有时候错位相减会减不出东西来，但是碰上没有求和方法的柿子要往这方面想！！

如果求和式中包含组合数，那么错位相减大概率可以成功。如果求和式中包含指标的定次幂，那么应该先展开一下搞出组合数。

$S_0(n)=1-2^{-(n-1)},S_k(n)=\binom{1}{k}-\binom{n}{k}2^{-(n-1)}+S_{k-1}(n)$

$S_j(n)$ $O(k)$ $O(k^2)$ $O(k^2)$ 的 60pts.

$O(k\log k)$ ，可以通过原题非加强版。

关于错位相减的总结：

$T_k(n)=\sum\limits_{i=0}^n \dbinom{i}{k}a^i$ $k$ 的递推式。
$X_k(n)=\sum\limits_{i=0}^n \dbinom{k}{i}a^i$ $\frac{k}{k-i+1}-\frac{k}{i}$ $n\ge k$ 时后面系数全是零，因此直接二项式定理即可。
$D_k(n)=\sum\limits_{i=0}^n\dbinom{n}{i}i^k$ 常幂展开，后面是二项式定理直接计算。
$Y_k(n)=\sum\limits_{i=0}^n a^ii^k$ 先常幂展开再错位相减即可。

$(1-\frac{1}{a})T_k(n)=\binom{n+1}k a^n-T_{k-1}(n)$

$D_k(n)=\sum\limits_{j=0}^k\begin{Bmatrix}k\\j \end{Bmatrix}n^\underline j2^{n-j}$

$Y_k(n)=\sum\limits_{j=0}^k\begin{Bmatrix}k\\j \end{Bmatrix}j!T_j(n)$

$\begin{Bmatrix}n\\m \end{Bmatrix}=\sum\limits_{i=0}^m\dfrac{(-1)^i}{i!}\dfrac{(m-i)^n}{(m-i)!}$ $a_i=\frac{(-1)^i}{i!},b_i=\frac{i^k}{i!}$ ，然后直接卷积即可。

$O(n\log n)$ $O(n)$ 。

$\sum_{i=0}^n\binom{i}{k}i^k$ $j$ $\sum_{i=0}^n\binom{i}{k}\binom{i}{j}$ ，这个柿子真的能做吗.../kk

[LOJ6608] 无意识的石子堆

$n\times m(n\le m)$ $2n$ 个棋子，求有多少种放棋子的方案，使得每个行每列都只有不超过两颗棋子。

$i$ $2(n-i)$ 列放了一个。

$\sum\limits_i \dbinom{m}{i}\dbinom{m-i}{2(n-i)}s[i]$ $s[i]$ $i$ 列放了两个的情况下，有多少种合法的行分配方式。

$s[i]$ $2n$ $n$ $2n-i$ $i$ $2n-2i$ 个盒子需要放一个小球。同一个盒子里面的小球必须异色，求放置方案数。

首先只需要强制所有盒子都不为空，然后插板，就能满足接近所有限制。唯一不满足的限制是一个盒子里面的小球必须异色。

$j$ $1$ 。

$s[i]=\dfrac{1}{2^n·2^i}\sum\limits_{j=0}^i(-1)^j \dbinom{i}{j}\dbinom{n}{j}j!2^j\times (2(n-i))!$ 。

$O(n\log n)$ ，只需要一次卷积，不过常数还是不小。

[LOJ6289] 花朵

$O(nm)$ ，可以拿到 37pts.

考虑如果是一个菊花，只有两种可能：选根，其它的全不选；不选根，其它的随便选。然后分治 FFT 一下，总共 52pts。

考虑如果没有摘掉的节点不相邻这个限制的话，相当于一个广义背包，可以直接分治 FFT 解决掉。

$A_u(x)$ $u$ $B_u(x)$ $u$ $A_u(x)=\prod_{v}[A_v(x)+B_v(x)]$ $B_u(x)=v_ux\prod_v A_v(x)$ 。

$[x^m](A_1(x)+B_1(x))$ 。

那么一条链也做完了，这样有 67pts.

生成函数的乘法是可以交换的，考虑链分治，把树剖成若干链，然后按照 dfs 序的倒序处理每一条链。先遍历一遍，把链上每个点在这个时候真实的多项式求出来，然后对整条链带权分治 FFT。

$O(\log n)$ $O(n\log ^3n)$ 。

[AGC005F] Many Easy Probs

$i$ $1$ 的贡献，当且仅当有两个点之间的路径会经过这个点。

$\binom{n}{i}-\sum_t\binom{sz[t]}{i}$ ，这里上方子树我们也认为是一个子树。

$ans[i]=\sum\limits_{j=1}^n\left[ \dbinom{n}{i}-\sum\limits_{k:j}\dbinom{sz[k]}{i}\right]$

$sz[]$ 分类，得到：

$ans[i]=n \dbinom{n}{i}-\sum\limits_{k=1}^n cnt[k]\dbinom{k}{i}$

$cnt[n]$ $n$ ：

$ans[i]=-\sum\limits_{k=1}^n cnt[k]\dbinom{k}{i}=\dfrac{-1}{i!}\sum\limits_{k=1}^n \dfrac{cnt[k]k!}{(k-i)!}$

这样就直接卷积。

19

[LG P5824] 十二重计数法

$n$ $m$ 个盒子里。

$m^n$
$n!\dbinom{m}{n}$
$m!\begin{Bmatrix}n\\m \end{Bmatrix}$
$\dbinom{n + m-1}{m-1}$
$[n\le m]$
$\dbinom{n-1}{m-1}$
$[x^n]\dfrac{1}{(1-x)^m}$
$[x^n](1+x)^m$
$[x^n]\dfrac{x}{(1-x)^m}$
球全部相同，盒子全部相同：整数拆分，等价于背包，多项式 exp
$[n\le m]$
$m$ 个球，和 10 等价

[CF1096G] Lucky Tickets

$k$ $n/2$ $0\le d_i\le n/2$ $\sum d_i=n/2$ $k$ $d_i$ $\dfrac{(n/2)!^2}{(d_1!d_2!...d_k!)^2}$ 的和。

$A(x)=\sum\limits_{i=0}^{n/2} \dfrac{x^i}{i!^2}$ $(n/2)!^2[x^{n/2}]A^k(x)$ $O(n\log n\log k)$ $O(nk\log n)$ 。

$k$ $n$ $k+n-1$ 项。

$A(x)=\sum\limits_{t\in S}x^t$ $A^{n/2}(x)$ 的各项系数的平方和。

$B(x)=A^m(x)$ $x$ $A^m(x) \,\text dx = [A^m(x)]'A'(x)=mA^{m-1}(x)A'(x)$ 。

$B'(x)=mA^{m-1}(x)A'(x)$ $B'(x)A(x)=mA'(x)B(x)$ 。

$A(x)=\sum\limits_{i\ge 0} a_ix^i,B(x)=\sum\limits_{i\ge 0} b_ix^i$

$A'(x)=\sum\limits_{i\ge 0}(i+1)a_{i+1}x^i,B'(x)=\sum\limits_{i\ge 0}(i+1)b_{i+1}x^i$

$\sum\limits_{j=0}^i(j+1)b_{j+1}a_{i-j}=\sum\limits_{j=0}^i m(j+1)a_{j+1}b_{i-j}$ $b_{i+1}$ $O(nk^2)$ 递推出每一项系数了。

$b_0=a_0^m, b_n=\dfrac{1}{na_0}\left[m\sum\limits_{j=0}^{n-1}(j+1)a_{j+1}b_{n-1-j}-\sum\limits_{j=1}^n a_j(n-j+1)b_{n-j+1}\right]$

$b_i$ $nk$ $a$ $k$ $O(nk^2)$ 。

[PKUWC2018] 猎人杀

对于一个整体，它出现在 1 之前或之后的概率与其它元素是毫无关系的，只跟这个整体的权值和和 1 的权值有关。

考虑算“某个集合里的所有元素均在 1 之前出现”的概率并不好算，因为分母每时每刻都是在变的，这时候我们不能把这些元素当做一个整体。

$\dfrac{w_1}{sum+w_1}$ $sum$ 表示这个整体的权值和。

$S$ $1$ 之后被选到，答案应当是：

$\sum\limits_S(-1)^{|S|}\dfrac{w_1}{sum(S)+w_1}$

$f[i,j]$ $i$ $j$ $\sum\limits_{i=0}^{n-1} (-1)^i\sum\limits_{j}f[i,j]\dfrac{w_1}{j+w_1}$ $O(n|V|)$ ，有 50pts。

$f[j]$ $j$ $\sum\limits_{j}f[j]\dfrac{w_1}{j+w_1}$ 。

$f[j]$ $j$ $-1$ $f[j]=[x^j]\prod\limits_{i=2}^n(1-x^{w_i})$ 。

$w_i$ $O(|V|\log^2|V|)$ 。

枚举子集容斥的容斥系数和是可以背包，并且可以写出生成函数的！！这一点一定要记清楚。

[XXI Opencup GP of Tokyo H] Harsh Comments

$n$ $a_i$ $m$ $b_i$ $\frac{a_i/b_i}{s}$ $s$ 是剩余所有物品的权值和。求你把所有 A 物品扔光的期望操作次数。

$S$ $S$ $|S|-1$ 。

$S$ $S$ $S$ $\sum\limits_{x\not\in S}\dfrac{v_x}{v_x+sum(S)}$ 。

$\sum\limits_{S\neq \emptyset}(-1)^{|S|-1}\sum\limits_{x\not\in S}\dfrac{v_x}{v_x+sum(S)}$ 。

$sum(S)$ $sum(S)$ $x$ $\sum\limits_{x}\sum\limits_{S\neq \emptyset}(-1)^{|S|-1}\dfrac{v_x}{v_x+sum(S)}$ 。

$x$ $f[]$ $x$ $\sum\limits_{j}\dfrac{f[j]v_x}{j+v_x}$ $f[j]$ $j$ 的集合的容斥系数和。

$-1$ $f[j+v_i]\gets-f[j]$ 。

$(1-x^{v_i})$ $x$ 的时候模拟除法即可。

$O(n^2|V_A|)$ 。

20

[CF755G] PolandBall and Many Other Balls

白给好题

$n$ $i\in[1,k]$ $i$ 组的方案数。

$n-1$ $j$ $O(n\log n)$ 。

然后再选出连续一个的放置方案，发现没法卷积...

$i$ $j$ $j$ $n-j$ $i$ $i$ $j$ 个把它变成两个，后面选择的位置顺次向后推移，可以发现这和原问题等价。

$ans[i]=\sum\limits_j \dbinom {n-j}i\dbinom i j=\sum\limits_j \dfrac{(n-j)!}{(n-j-i)!j!(i-j)！}$

发现还是没法卷积...

$\sum_j\binom {n-j}i\binom i j$ $i$ $i$ 个，需要不会选重。

$j$ 个选重了，得到另一种表示：

$ans[i]=\sum\limits_j(-1)^j\dbinom{i}{j}\dbinom{n-j}{i-j}2^{i-j}$

$n$ $j$ $n!$ 就可以做了，记住这个技巧！！

$ans[i]=i!n^\underline i\sum\limits_j \dfrac{(-1)^j}{j!n^\underline j}\times \dfrac{2^{i-j}}{[(i-j)!]^2}$

$O(n\log n)$ 。

D5 A

$f(1)=1,f(p^k)=p^k+1$ $f$ 的前缀和。

$\sum\limits_i i\sum\limits_{ij\le n}[(i,j)=1]$ ，然后就是莫比乌斯反演那一套...

21

D6 B

如果行列式的某行或者某列有公因子，可以把它提出来计算。

矩阵和它的转置的行列式相等。

$\det \begin{vmatrix} \binom{a_1+1}{1}&...&\binom{a_1+n}{n}\\\vdots&\ddots&\vdots\\\binom{a_n+1}{1}&...&\binom{a_n+n}{n}\end{vmatrix}$ 。

提公因子得：

$=\dfrac{1}{2!...n!}\det \begin{vmatrix} (a_1+1)&...&(a_1+1)^\overline n\\\vdots&\ddots&\vdots\\(a_n+1)&...&(a_n+1)^\overline n\end{vmatrix}$

$a_i+1$ $j\in[1,n]$ $(a_i+1)^j$ 的形式。

$a_i+1$ $a_i+1$ $\det F=\prod\limits_{i<j}(x_j-x_i)=\prod\limits_{i<j}(a_j+1-a_i-1)$ ，注意这里一定是大下标减掉小下标。

$ans=\dfrac{(a_1+1)...(a_n+1)}{2!..n!}\det F$

$a_j-a_i$ $a_i$ $-a_i+\max a_i$ $i,j$ 会被算两遍，一遍正的一遍负的。因为我们知道结果总是正的，所以枚举一半即可。

D6 C

$m$ 的序列。

考虑可以通过每次选“最靠前的能选的下一个数字”来构造双射，这样可以不重不漏。
$n$ $m$ $i$ $i-1$ $i$ $m$ 后面的位置随意。

记住上面两种方法！！选最前面的那个作为代表点，剩下的部分的方案数实际上可以表示出来！！

$m$ $f(n,m)$ $[1,m]$ $n$ $m$ 的序列有多少个，那么：

$f(n,m)=\sum\limits_{i=m}^n \dbinom{i-1}{m-1}m^{n-i}(m-1)^{i-m}$

$n$ 的卷积，当然了这对原问题并没有帮助。

$m^{n-i}$ 这一部分每个数字出现次数都是相等的，那么前面这一部分满足吗？

考虑所有情况下，每个数字不能出现的段长的和一定是相等的！这可以通过交换位置问题不变来理解。所以前面部分每个数字出现次数也是相等的。

$n,m$ $\frac{n}{m}f(n,m)$ 。

$O(n^2)$ $n\le 5\times 10^4$ 依然不能做。不会/kk

22

[CF643G] Choosing Ads

$(v,s)$ $v$ $s$ $v_l=v_r$ $(v_l,s_l)·(v_r,s_r)=(v_l,s_l+s_r)$ $(v_l,s_l)·(v_r,s_l)=(\arg\max s,\max s-\min s)$ 。

$k=\lfloor 100/q \rfloor$ $k$ $k$ 的那些元素没用，维护差值即可。

注意区间众数和区间带修众数是一个莫队问题。

[ARC093D] Dark Horse

$1$ $p_1=1$ $2^n$ 。

$n-1$ $G_i=\begin{Bmatrix} p_{2^{i-1}+1},..., p_{2^i}\end{Bmatrix}$ $A=\begin{Bmatrix} a_1,...a_m\end{Bmatrix}$ 中。

$S\subseteq \begin{Bmatrix}G_i\end{Bmatrix}$ $S$ $G_x$ $A$ 中的方案数。

$A_i$ $A_i$ $A_i$ $A_i$ $G_x$ $>A_i$ $G_x$ 选取情况有关。因此可以倒着做状压 DP。

$O(nm2^n)$ 。

[CF708E] Stu Camp

$n^3$ $f[i,l,r]$ $i$ $i$ $[l,r]$ $O(n^5)$ 的。

$pre[l]=pre[l-1]+\sum\limits_{j=1}^l f[i,j,l],suf[r]=suf[r+1]+\sum\limits_{j=r}^m f[i,r,j]$ $O(n^3)$ $f[i+1,l,r]=(pre[m]-pre[l-1]-suf[r+1])\binom{k}{l-1}p^{l-1}(1-p)^{k-l+1}\binom{k}{m-r}p^{m-r}(1-p)^{k-m+r}$ 。

$A_l=\binom{k}{l}p^{l}(1-p)^{k-l},B_r=\binom{k}{m-r}p^{m-r}(1-p)^{k-m+r}$ ，这两个直接线性预处理，那么：

$f[i+1,l,r]=(pre[m]-pre[l-1]-suf[r+1])A_{l-1}B_r$

$\begin{aligned}pre'[l]&=pre'[l-1]+B_l\sum\limits_{j=1}^l A_{j-1}pre[m]-A_{j-1}pre[j-1]-A_{j-1}suf[l+1]\\&=pre'[l-1]+B_l(pre[m]A^s_{l-1}-suf[l+1]A^s_{l-1}-C_l)\end{aligned}$

$\begin{aligned}suf'[r] &= suf[r+1]+A_{r-1}\sum\limits_{j=r}^m B_j pre[m] -B_jpre[r-1]-B_jsuf[j+1]\\&=suf[r+1]+A_{r-1}(pre[m]B^s_{r} -pre[r-1]B^s_r- D_r)\end{aligned}$

$pre,suf,pre', suf',A,B,A^s,B^s,C,D$ 即可。

$pre[m]=suf[1] =1$ $pre[m]$
$pre'[l]=pre'[l-1]+B_l(pre[m]A^s_{l-1}-suf[l+1]A^s_{l-1}-C_l)$
$suf'[r] =suf[r+1]+A_{r-1}(pre[m]B^s_{r} -pre[r-1]B^s_r- D_r)$
$A_l=\binom{k}{l}p^{l}(1-p)^{k-l},l\in[0,m-1]$
$B_r=\binom{k}{m-r}p^{m-r}(1-p)^{k-m+r},r\in[1,m]$
$A^s$ $A$ 的前缀和
$B^s$ $B$ 的后缀和
$C_l=C_{l-1}+A_{l-1}pre[l-1]$
$D_r=D_{r+1}+B_rsuf[r+1]$

$O(n^2)$ 。

[雅礼集训 2018 Day4] Magic

$f[i,j,k]$ $i$ $j$ $k$ $n^4$ $n^3$ 的，然后 10 个点到手。

$\prod_i a_i!$ 。

$f(k)$ $k$ $g(k)=\sum\limits_{j=k}^{n-1}(-1)^{j-k}\dbinom j kf(j)$ 。

$n$ $k$ $n-k$ $i$ $j$ $n$ $n-k$ 个同色排列段的方案数。

$t[i,j]$ $i$ $j$ $t[i,j]=a_i!\binom{a_i-1}{j-1}/j!$ $A_i(x)$ $t[i,j]$ $f(k)=(n-k)![x^{n-k}]\prod_iA_i(x)$ 。

$A_i(x)$ $O(n\log ^2n)$ 。

23

[CF1349F2] Slime and Sequences

草，某题居然是原题

$m$ $\sum_{i=m}^n \binom{i-1}{m-1}(m-1)^{i-m}m^{n-i}$ 。

$m$ $[1,m]$ $m^{n-i}$ 这部分显然相同，前面部分一个数字在所有情况下能出现的段长和相同。

$\frac{n}{m}\sum_{i=m}^n \binom{i-1}{m-1}(m-1)^{i-m}m^{n-i}$ $O(n^2)$ ，Easy Version 解决。

不一样！！比如 2 3 1 2 这样也是合法的。

$f(k)$ $k$ $\sum_{i=0}^{n-1}(-1)^if(i)$ $f(k)$ 怎么数啊....

$i$ $i-1$ 个括号的最小值。把每个括号降序排列，可以发现每个括号实际上是一个排列的极长下降子段。显然这是双射。

$n!$ 。

$x$ $n!$ $x$ $n$ $k$ 个连续下降段的方案数怎么算。

$\left\langle\begin{matrix}n\\k \end{matrix}\right\rangle$ $n$ $k$ $a_i<a_{i+1}$ 的排列数。

$\left\langle\begin{matrix}n\\k \end{matrix}\right\rangle=\left\langle\begin{matrix}n\\n-k-1 \end{matrix}\right\rangle$ ，且有递推式：

$\left\langle\begin{matrix}n\\k \end{matrix}\right\rangle=(k+1)\left\langle\begin{matrix}n-1\\k \end{matrix}\right\rangle+(n-k)\left\langle\begin{matrix}n-1\\k-1\end{matrix}\right\rangle$

$<$ $n$ ，上升个数不变；其他情况上升个数减一。

$\left\langle\begin{matrix}0\\n \end{matrix}\right\rangle=\left\langle\begin{matrix}n\\n \end{matrix}\right\rangle=[n=0],\left\langle\begin{matrix}n\\0 \end{matrix}\right\rangle=1$ 。

$x$ $x-1$ $x$ 段下降段的长度和？

$m$ $\sum\limits_{i=1}^n\dbinom{n}{i}\left\langle\begin{matrix}i\\m-1 \end{matrix}\right\rangle(n-i)!$ 。

$O(n^2)$ 。

$n!$ 。
$n^m=\sum\limits_{i=0}^m\left\langle\begin{matrix}m\\i \end{matrix}\right\rangle\dbinom{n+i}{m}$

口胡证明是构造一个从排列到序列的映射，但是细节上出了点小问题。具体数学上好像有个代数证明。

$(x+y)^\underline n=\sum_k \binom n kx^\underline ky^\underline{n-k}$ ，上升幂同理。

$f(k)$ $n$ $k$ 个间隔是小于的方案数，那么：

$\left\langle\begin{matrix}n\\m \end{matrix}\right\rangle=\sum\limits_{i=m}^{n-1}(-1)^{i-m}\dbinom{i}{m}f(i)$

$f(k)$ $f(k)=n![x^n](e^x-1)^{n-k}$ 。不会搞/kk

[LOJ6271] 生成树求和

$O(\log_3c)$ ，然后对于这一位，需要计算所有“生成树边权在三进制下不进位加法和”在十进制下的和。

$0,1,2$ $t_u(x)=x^{c_u}$ $A(x)=\sum_T\prod_u t_u(x)$ $A(x)\bmod x^3-1$ 这个多项式。

$0,1,2$ $cnt[0],cnt[1],cnt[2]$ $x(x\ge 0)$ $3^x(0·cnt[0]+cnt[1]+2·cnt[2])$ 。

$cnt[1],cnt[2]$ $\omega_3$ 代入多项式求值即可，也就是单位根反演：

$\sum\limits_{i\ge 0}[3|(i-c)]a_i=\sum\limits_{k=0}^2\omega_3^{-ck}\sum\limits_{i\ge 0}a_i\omega_3^{ki}$

$\omega_3=e^{\text i\frac{2\pi}{3}}=-\frac{1}{2}+\text i\frac{\sqrt 3}{2}$ $\text i^2=-3$ 扩域即可。

$O(3n^3\log_3c)$

$u$ $a[u,v]$ $u,v$ 的边权！！

lg-blog

[ARC096C] Everything on It

$k$ $k$ $i$ 个选出的子集里面，应该是：

$\sum\limits_{k=0}^n(-1)^k \dbinom{n}{k}2^{2^{n-k}}\sum\limits_{j=0}^k\dbinom{k}{j}\sum\limits_{i=1}^j \begin{Bmatrix}j\\i \end{Bmatrix}(2^{n-k})^i$

$=\sum\limits_{k=0}^n (-1)^k\dbinom{n}{k}2^{2^{n-k}}\sum\limits_{i=1}^k(2^{n-k})^i\sum\limits_{j=i}^k\dbinom{k}{j}\begin{Bmatrix}j\\i \end{Bmatrix}$

$\sum\limits_{k}\dbinom{n}{k}\begin{Bmatrix}k\\m \end{Bmatrix}=\begin{Bmatrix}n+1\\m+1\end{Bmatrix}$ 。

$n$ $m$ $\begin{Bmatrix}n+1\\m+1\end{Bmatrix}$ 。

$=\sum\limits_{k=0}^n (-1)^k\dbinom{n}{k}2^{2^{n-k}}\sum\limits_{i=1}^k(2^{n-k})^i\begin{Bmatrix}k+1\\i+1\end{Bmatrix}$

$O(n^2)$ 。

[CF1295F] Good Contest

$[1,3] [5,8][9,10]$ $[0,1),[1,4),[4,5)[5,9)[9,11)$ 这些段。

$f[i,j]$ $i$ $j$ $j$ $[k,i],k\in[1,i]$ $f[i,j]\gets f[k-1,j+1]\binom{len_j+i-k}{i-k+1}$ $[k,i]$ $j$ 段内。

$g[i]=\binom{T+i}{i+1}$ $g[0]=T,g[i]=\frac{T+i}{i+1}g[i-1]$ $j$ 之后直接预处理即可。

$O(n^3)$

24

训练 34 C

$a$ $k$ $a$ $k$ $1$ 的代价将任意一个位置减一，问最小花费多少代价。

$i$ $sum(j,i)$ $j$ $i$ $sum(j,i)$ $k$ 的部分减掉就好了。感性理解一下这样贪很对，然后就有了线性做法。

往上套区间查询？？

训练 34 B

$s$ $O(|s|\sqrt{|s|})$ 。

$O(|s|\sqrt{|s|})$ 。然后 BIT 大力就是 50，改成差分草了 80.../jk

考虑每次向上覆盖颜色，实际上是等价于一个 access，然后就是树点涂色这个题，直接大力树剖覆盖难写的跟 shi 一样。

$O(n\log n)$ 。

训练 34 A

考虑如果斜率都知道，那么这题就做完了，然后爆搜就是 50pts.

$|x_i/y_i-y_i/x_i|$ 排序的话，那么最中间的向量一定是最靠前的那个，之后的每一个一定在凸包的左边或者右边扩展。然后就可以 DP？

$\tan$ ，用最大的那个排序就好了，之后直接 DP 也是对的/fad 玄学...

[CF618E] Robot Arm

$v_i=(x_i,y_i)$ $\lambda_i= (\theta_i,l_i)$ $\lambda_i$ $v_i$ ，然后合并上去，就没了。

错了。一次修改不止改了一个向量，应该是一个后缀的所有向量做旋转笛卡尔系。

$y$ 个向量的起始为坐标原点，在笛卡尔系内旋转向量。

$\theta$ 角的旋转矩阵是：

$M(\theta)=\begin{vmatrix}\cos \theta&-\sin\theta\\ \sin\theta&\cos\theta \end{vmatrix}$

$\begin{vmatrix}x&y \end{vmatrix}M(\theta)=\begin{vmatrix}x'&y' \end{vmatrix}$ ，推导可以直接考虑辐角形式，然后恒等变换搞出来。

所以直接后缀打矩阵 tag 即可。

[AGC034F] RNG and XOR

min-max 容斥。

$s,i\subseteq s$ $\mathbb E'(i)$ $i$ $T$ $\mathbb P(T)=\sum\limits_{j\cap T\neq \emptyset}\mathbb P(j)=1-\sum\limits_{j\subseteq\complement T}\mathbb P(j)$ ，有：

$\mathbb E'(i)=\sum\limits_{T\subseteq i,T\neq \emptyset}(-1)^{|T|-1}1/\mathbb P(T)$

$\mathbb E'(i)=\sum\limits_{i\subseteq S}\mathbb E(S)$

那么子集反演：

$\mathbb E(i)=\sum\limits_{i\subseteq S}(-1)^{|i|-|S|}\mathbb E'(S)$

$O(n2^n)$ 。

错了！这么算不对，再 min-max 容斥一遍也不对！列方程是啥东西啊/kk

25

35 A

考虑把一个串合并到它的最小循环节上面去，然后剩下的串数实际上就是答案。也就是说，要求最小循环节等于本串的数的个数。

$n$ $c^n$ $d|n,d<n$ $d$ 的最小循环节等于本串的数的个数，因为这些串中的每一个的若干次方都可以唯一对应一个不合法串。

$n$ $n$ 即可。

$f[n]=c^n-\sum\limits_{d|n,d<n}f[d]$ $\sum\limits_{i=1}^L f[i]/i$ 。

$O(n\ln n)$ ，这已经很快了，大多数情况下是足够用的。但是在某些特殊情况下，这还可以进一步优化，这种情况是计算狄利克雷前缀和：

$g[n]=\sum\limits_{k|n}f[k]$

$i=\prod_k p_k^{\alpha_k},j=\prod_kp_k^{\beta_k}$ $i$ $j$ $\forall k,\alpha_k\le \beta_k$ 。

$O(n\log\log n)$ 。

先枚举维数，然后从小到大枚举数字，做前缀和。注意必须从小到大，实际上就是这个维度上的前缀和。

整理一下三种变式：

$g[n]=\sum\limits_{k|n}f[k]$


xxxxxxxxxx
2
1
for(int i = 1; i <= p[0]; i++) for(int j = 1; j * p[i] <= n; j++) 
2
    f[j * p[i]] = add(f[j * p[i]], f[j]);

$g[n]=f[n]-\sum\limits_{d|n,d<n}g[d]$


xxxxxxxxxx
2
1
for(int i = 1; i <= p[0]; i++) for(int j = n / p[i]; j; j--) 
2
    f[j * p[i]] = add(f[j * p[i]], P - f[j]);

$g[n]=f[n]+\sum\limits_{d|n,d<n}g[d]$

这个好像不能做/kk

后面两个是半在线的，注意区分一下。

35 C

$s$ $s$ $s'$ $(s')^r$ $s$ 的每个前缀的本质不同回文串数。

第一个和第三个都很好求，考虑第二个。

$s'$ $(s')^r$ $O(n^2)$ 。

$s'$ $(s')^r$ $(s')^r$ $l$ $u$ $\max0,(\min len[i],l)-len[nxt[u]]$ $O(n^2)$ 。

[CF1264D2] Beautiful Bracket Sequence

考虑给定一个括号串，如何求它的深度。实际上就是找一个间隔，使得间隔左边的左括号个数等于间隔右边的右括号个数，然后答案就是间隔左边的左括号个数。

$f[i,j]$ $i$ $j$ $i,j$ $f[i,j]·g[i+1,j]$ $O(n^2)$ 。

$i$ ，前后的转移系数是：

$\sum\limits_{j} j\dbinom{pc[i]}{j-pre[i]}\dbinom{sc[i+1]}{j-suf[i+1]}$

$pre[i]$ $i$ $suf[i]$ $i$ $pc[i]$ $i$ $sc[i]$ $i$ 后面的问号个数。

换下枚举指标，实际上等于：

$pre[i]\dbinom{pc[i]+sc[i+1]}{pc[i]+pre[i]-suf[i+1]}+pc[i]\dbinom{pc[i]+sc[i+1]-1}{pc[i]+pre[i]-suf[i+1]}$

26

幂级数的收敛域和收敛半径：zhihu

$\sum_{i\ge 0}a^i=\frac{1}{1-a}$ $(-1,1)$
$[-\phi,\phi)$

$<1,1,1,...>$ 的 OGF 对矩阵存在解析意义，也就是：

$\sum\limits_{i\ge 0}M^i=\dfrac{I}{I-M}$

这个还是记住吧...

$n$ $A$ $\det A\neq0$

zhihu $A$ $A$ 的逆矩阵。

$M_{i,j}$ $A$ $i$ $j$ $n-1$ $A_{i,j}=(-1)^{i+j}M_{i,j}$ $a_{i,j}$ 的代数余子式。
$A'=(A_{i,j})_{n\times n}$ $A$ 的伴随矩阵。

$A$ $A$ $A$ $O(n^3)$ $A$ $A$ 的行列式。

行列式为零等价于有一行没有主元，这个可以直接在高斯消元的时候判断。

36 B

考虑递推式：

$\begin{align}a_n&=xa_{n-1}-yb_{n-1}\\ a_n&=xb_{n-1}+ya_{n-1} \end{align}$

$a_0=1,b_0=0$ $\sum_{i=0}^m \frac{a_ib_i}{c^i}$ $m$ $\infty$ ，此时需要判断幂级数是否收敛，并求它的收敛域。

$m\neq \infty$ 的情况，但是注意矩阵不存在逆的时候，我们并没有办法判断这个东西是否收敛，以及求它的收敛域，这是矩阵逆的性质导致的。

$z_n=a_n+b_ni$ $z_{n+1}=(xa_n-yb_n)+(xb_n+ya_n)\text i$ $z_{n+1}/z_n=(x+y\text i)$ 。

$a_n=\text{Re}(x+y\text i)^n, b_n=\text{Im}(x+y\text i)^n$ ，这是一个类似于多元生成函数的性质，我们尝试代入求和然后直接求出一个闭合形式。

$[(x+y\text i)^n]^2=(a_n+b_n\text i)^2=a_n^2-b_n^2+2a_nb_n\text i$

$\dfrac{1}{2}\sum\limits_{i=0}^m \dfrac{\text{Im}(x+y\text i)^{2n}}{c^n}=\dfrac{1}{2}\text{Im}\sum\limits_{i=0}^mz^n=\dfrac{1}{2}\text{Im}\dfrac{1-z^{n+1}}{1-z}$

$z=[(x^2-y^2)+2xy\text i]/c$ ，这样有限随便做。

$\frac{1}{2}\text{Im}\frac{1}{1-z}$ $(-1,1)$

$|z|<1$ 。

$|z|\ge 1$ 那么直接输出 error，否则直接套柿子求逆。注意复数求逆也满足费马小定理之类的规律，也就是可以直接拿共轭那一套来求逆，也可以直接快速幂。

$\sum_{i=0}^na^i$ ，可以奇偶分类：


xxxxxxxxxx
5
1
Func Sum(a, n){ // sum_{i=0...n-1} a^i
2
    if(!n) return 1
3
    if(!(n & 1)) return (1 + a) * Sum(a, n >> 1)
4
    return 1 + (a + a * a) * Sum(a, n >> 1)
5
}

$\log$ 。

36 C

$(i,j,k)$ $i<j<k$ $a_i+a_k=a_j$ 。

$B$ $j$ ，然后分类讨论：

$i,j,k$ $O(nB)$
$i,j,k$ $j$ $O(nB)$
$i,j,k$ $i,k$ $j$ $O(\frac{n}{B}m\log m)$

$O(nB+\frac{n}{B}m\log m)$ $B$ $\sqrt{m\log m}$ $O(n\sqrt{m\log m})$ 。

依然很卡常。

27

$O(n^2)$ 级别的，没有更低的上界！

$nxt[]$ 链可能会有一些奇怪的复杂度...

NOI OL A

数列：0110100110010110...

的分布规律是，popcount(x)%2=1 的位置是某种数字，popcount(x)%2=0 的位置是另一种数字。

还需要一个结论：

$n$ $0,...,2^n-1$ $i\in[0,n-1]$ $i$ 次方和相等。

$g[i,j,0/1]$ $2^i$ $j$ 次方之和，考虑转移：

$g[i+1,j,0]=g[i,j,0]+\sum\limits_{t=0}^j \dbinom{j}{t}2^{i(j-t)}g[i,t,1]$

$O(nk^2)$ $g[]$ 的值。

$f(i,j,0/1,d)$ $g[i,j,0/1]$ $d$ 个位置，有：

$f(i,j,0/1,d)=\sum\limits_{t=0}^j\dbinom{j}{t}d^{j-t}g[i,t,1/0]$

注意这里 0/1 恰好反转。然后就能拼出答案了。

$S[i,j]=\sum_{t=0}^{2^i-1}t^j$ $g[i,j,0]=g[i,j,1]=\frac{S[i,j]}{2}(i\ge j)$ 。

$i\le k$ $g[]$ $O(k^3)$ $O(k^2)$ 。

$i>k$ $g[]$ $O(k)$ $O(nk+k^3)$ ，大概有 80pts。不会/kk

29

NOIO / NOIP 答辩题选做

[NOIO2021TG A] 愤怒的小 N

$N=2^n$ $\sum_{i=0}^{N-1}f(i)[pop[i]\bmod 2=1]$ 。这样拆分：

$2ans=\sum\limits_{i=0}^{N-1} f(i)-\sum\limits_{i=0}^{N-1}(-1)^{pop[i]}f(i)=A-B$

前面是自然数幂和问题：

$A=\sum\limits_{j=0}^{k-1} a_j\sum\limits_{i=0}^{N-1}i^j=\sum\limits_{j=0}^{k-1}a_j\sum\limits_{t=0}^j \begin{Bmatrix}j\\t \end{Bmatrix}t!\sum\limits_{i=0}^{N-1}\dbinom{i}{t}$

$=\sum\limits_{j=0}^{k-1}a_j\sum\limits_{t=0}^j \begin{Bmatrix}j\\t \end{Bmatrix}\dfrac{N^{\underline {t+1}}}{t+1}$

$N$ $O(k^2)$ 。

$n$ $x$ $2^x$ 个位置的答案，然后向右边递归分治（实际上循环模拟即可）。

$g[i,j,0/1]$ $2^i$ $j$ 次方之和，有转移：

$g[i,j,0/1]=g[i-1,j,0/1]+\sum\limits_{t=0}^j \dbinom{t}{j}2^{(i-1)t}g[i-1,j-t,1/0]$

$d$ $2^x$ $B$ $o$ $sum(d,x,o)$ ，那么有：

$sum(d,x,o)=\sum\limits_{j=0}^{k-1} a_j\sum\limits_{t=0}^j\dbinom{j}{t}d^t\left(g[x,j-t,o]-g[x,j-t,o\oplus 1] \right)$

$x\ge k$ $t\in[0,k-1]$ $g[x,t,0]=g[x,t,1]$ $sum(d,x,o)=0$ ，这时候直接 return 0 即可。

$k$ $O(n+k^3)$ 。

[NOIO2021TG C] 岛屿探险

$\min b_i,d=d$ $a_i\oplus c\le d$ $a_i$ 有多少，这是经典问题。

建立可持久化 Trie，然后讨论：

$c,d$ $1$ ，那么右子树都可以，递归左子树；
$c$ $1$ $d$ $0$ ，那么只能右子树；
$c$ $0$ $d$ $1$ ，那么左子树都可以，递归右子树；
$c,d$ $0$ ，那么只能左子树。

$\min b_i,d=b_i$ $(a_i,b_i)$ $c$ 。

$a_i\oplus c\le b_i$ $c$ $(a_i,b_i)$ ，然后讨论：

$b_i$ $0$ ，那么这个高位没有贡献，递归左子树；
$b_i$ $1$ $a_i$ 这一位对应的子树有贡献，递归另一个子树。

$c$ $c$ 建立了 Trie 然后考虑贡献。

这样就有大概 55pts.

$d$ 排序。

$(a_i,b_i)$ $b_i$ $\log n$ $n$ $O(\omega)$ $O((n+q)\log n\omega)$ 。

30

[HDU5390] Tree

总结下拿线段树分治解决可持久化问题的思路。

$O(n\log ^2n)$ $O(\log n)$ 层每层的一个节点，也就是在操作序列里面加一项“删除...插入...”。

$O(n\log^2 n\omega)$ $O(n\omega)$ 。

树剖常数小，大力松一松。

solu

[LG P5807] Which Dreamed It

有向图的欧拉回路存在当且仅当每个点的入度等于出度。几个计数定理：

（矩阵树定理）无向图的生成树个数等于基尔霍夫矩阵的任意一个降一阶主子式。有向图的生成树个数等于基尔霍夫矩阵删掉根所在阶的主子式。
$S$ $T$ $p$ $S_i\to T_{p_i}$ $n$ $\det (a_{i,j})_n$ $a_{i,j}$ $S_i\to T_j$ 的路径数。
$\text{ec}(G)$ $G$ $t_s(G)$ $G$ $s$ $\text{ec}(G)=t_s(G)\prod\limits_v(\text{deg}(v)-1)!$ 。

这里欧拉图指存在欧拉回路的图，默认不允许存在空点。两条欧拉回路不同，当且仅当经过边形成的环旋转不同构。

无向图的基尔霍夫矩阵是“每个点相邻边的权值和矩阵”减去边权邻接矩阵。

有向图类似：如果要算外向树，那么相邻边只统计入边；否则只统计出边。

模数是质数！!1

[JSOI2018] 战争

首先存在两个三角形有交就一定存在两个四边形有交....然后等价于两个凸包有交。

$B$ $d$ $B$ $\exist a\in A,b\in B,b+d=a$ 。

$d$ $D$ $D$ $A,(-B)$ 的闵可夫斯基和。

$A,B$ $A,B$ 的边构成。

$O(|A|+|B|)$ 的。

考虑如何求出这个凸包，可以发现这个凸包就是把两个凸包上的边极角排序之后顺次连接起来。先把两个凸包都用向量表示，然后把向量合起来极角排序，定义象限序为“四 < 一 < 二 < 三”然后排序，然后维护出和凸包横坐标最小的那个点，然后按照排序后的向量转一圈就求出来了。

考虑如何判断一个点在凸包内部，找到这个点横坐标处的上凸壳上的边和下凸壳上的边即可，然后叉积随便搞搞。

写麻烦了......

$x$ $y$ 降序，凸包从下凸壳转到上凸壳。

$c_1=a_1+b_1$ ，接下来的点比较那条向量比较靠下即可。

判断一个点在凸包内部，可以把凸包上所有点和查询点都减去第一个点的坐标。这样凸包上所有点在一个半平面内且按照极角序排列，可以直接二分找到现在查询点在哪一个三角剖分里面，就可以判断了。

注意可以在凸包后面多留一个点（也就是第一个点）来避免 border case。

$O(n+m+q\log nm)$


xxxxxxxxxx
40
1
class POI{
2
  public: LL x, y;
3
    POI operator + (const POI &o) const {POI r; r.x = x + o.x, r.y = y + o.y; return r;}
4
    POI operator - (const POI &o) const {POI r; r.x = x - o.x, r.y = y - o.y; return r;}
5
    LL operator * (const POI &o) const {return x * o.x + y * o.y;}
6
    LL operator ^ (const POI &o) const {return x * o.y - y * o.x;}
7
    bool operator < (const POI &o) const {return x ^ o.x ? x < o.x : y > o.y;}
8
} a[CN], b[CN], c[CN], stk[CN]; int n, m, q, top;
9
POI P(int x, int y) {POI r; r.x = x, r.y = y; return r;}
10
bool cmp(POI a, POI b) {return (a ^ b) > 0;}
11
void bd(POI a[], int &n){
12
    sort(a + 1, a + n + 1), top = 0;
13
    for(int i = 1; i <= n; i++){
14
        while(top > 1 && ((stk[top] - stk[top - 1]) ^ (a[i] - stk[top])) < 0) top--;
15
        stk[++top] = a[i];
16
    }
17
    for(int i = n - 1; i; i--){
18
        while(top > 1 && ((stk[top] - stk[top - 1]) ^ (a[i] - stk[top])) < 0) top--;
19
        stk[++top] = a[i];
20
    }
21
    n = top - 1; for(int i = 1; i <= n; i++) a[i] = stk[i];
22
}
23
void work(){
24
    c[top = 1] = a[1] + b[1], a[n + 1] = a[1], b[m + 1] = b[1]; 
25
    int i = 1, j = 1;
26
    while(i <= n || j <= m){
27
        if(j > m || (i <= n && ((a[i + 1] - a[i]) ^ (b[j + 1] - b[j])) > 0))
28
           c[top + 1] = c[top] + (a[i + 1] - a[i]), i++, top++;
29
        else c[top + 1] = c[top] + (b[j + 1] - b[j]), j++, top++;
30
    }
31
    n = top - 1;
32
    for(int i = 1; i <= top; i++) a[i] = c[i] - c[1];
33
    // for(int i = 1; i <= top; i++) printf("%d %d\n", c[i].x, c[i].y);
34
}
35
void qu(int x, int y){
36
    POI cur = P(x, y) - c[1]; int pos = upper_bound(a + 2, a + n + 1, cur, cmp) - a - 1;
37
    if(pos < 1 || pos > n) return 0;
38
    if(((cur - a[pos]) ^ (a[pos + 1] - a[pos])) <= 0) return 1;
39
    return 0;
40
}

31

争取字数破 3w！

38 B

$O(nm)$ $O(m)$ $O(1)$ 个位置是有效的，现在要判断方程是否有解。

考虑维护最简形式的线性基，然后加入一个向量。因为我们只需要对每个 1 所在的位置，确定这个位置是否有主元；如果没有，则确定主元并向上下消元。

$O(m)$ $O(\frac{m^2}{\omega})$ $O(\frac{m^3}{\omega})$ 。对每个向量，用 bitset::_Find_first() 和 bitset::_ $O(\frac{m}{\omega}+\text{popcount})$ $O(\frac{nm^2}{\omega}+\frac{m^3}{\omega})$ 的。

考虑判断有解，当且仅当所有未插入线性基的方程消元结束之后等号右边是零。

$O(n^2)$ $O(\frac{n}{\omega})$ $O(n)$ $O(\frac{n^2}{\omega})$ 。

这样在线维护比离线高斯消元的复杂度要优。

结论：任意一个八个方块的子矩形，如果都满足外围格子去掉四个角的异或和是零，那么就可以。

38 A

$1$ $n$ 就是答案。

$f[d,i,j]$ $i$ $d$ $d$ $j$ $g[d,i,j]$ 表示边权和。转移：

$f[d,i,j]=\sum\limits_{k=1}^{i-j}\dbinom{i-1}{j} f[d-1,i-j,k](2^k-1)^j2^{\binom j 2}$

$g[d,i,j]=\sum\limits_{k=1}^{i-j}\dbinom{i-1}j(2^k-1)^j2^{\binom j 2}\left(g[d-1,i-j,k]+jdf[d-1,i-j,k]\right)$

标号重分配！！！

$d$ 。

$F[i,j]=\sum\limits_{d}f[d,i,j]=\sum\limits_{k=1}^{i-j}\dbinom{i-1}{j}(2^k-1)^j2^{\binom j 2}F[i-j,k]$

$G[i,j]=\sum\limits_{d}g[d,i,j]$

$=\sum\limits_{k=1}^{i-j}\dbinom{i-1}j(2^k-1)^j2^{\binom j 2}G[i-j,k]+\sum\limits_{k=1}^{i-j}\dbinom{i-1}j(2^k-1)^jj\sum\limits_{d}df[d-1,i-j,k]$

$Fd[i,j]=\sum\limits_d df[d,i,j]$ ，后面的转移是：

$G[i,j]=\sum\limits_{k=1}^{i-j}\dbinom{i-1} j (2^k-1)^j2^{\binom j 2}G[i-j,k]+\sum\limits_{k=1}^{i-j}\dbinom{i-1}{j}(2^k-1)^j2^{\binom j 2}j(Fd[i-j,k]+F[i-j,k])$

$Fd[]$ 的转移是：

$Fd[i,j]=\sum\limits_ddf[d,i,j]=\sum\limits_{k=1}^{i-j}\dbinom{i-1}{j}(2^k-1)^j2^{\binom j 2}(Fd[i-j,k]+F[i-j,k])$

$F[1,1]=1,Fd[1,1]=G[1,1]=0$ $\frac{1}{n-1}\sum_j G[n,j]$ 。

[LG P4195] 扩展BSGS

exBSGS

之前想到过为什么适用性会和模数的素性有关，当时感性的给出了一个解释，现在看来好像犯了一个傻.....

重新理性推导一遍。BSGS 基于这个等价转换：

$x$ $a^x\equiv b\pmod P$ $k,t$ $a^{kB}\equiv ba^t\pmod P$ $k\ge 1 ,0\le t<B$ $kB-t=x$ ”的充分不必要条件。

$k$ $U$ $UB\ge 2\varphi(P)$ 。

等价于：

$k\ge 1 ,0\le t<B$ $a^{kB}\equiv ba^t\pmod P$ $k,t$ $a^{kB-t}\equiv b\pmod P$ ”的必要不充分条件。

$(i,j)=iP^j$ 的形式即可。

玄学，弃了。